package MiddlePractice;

import java.util.LinkedList;

import util.TreeNode;

public class Demo623 {
	//623. 在二叉树中增加一行
//	给定一个二叉树，根节点为第1层，深度为 1。在其第 D 层追加一行值为 V 的节点。
//
//	添加规则：给定一个深度值 D （正整数），针对深度为 D-1 层的每一非空节点 N，为 N 创建两个值为 V 的左子树和右子树。
//
//	将 N 原先的左子树，连接为新节点 V 的左子树；将 N 原先的右子树，连接为新节点 V 的右子树。
//
//	如果 D 的值为 1，深度 D - 1 不存在，则创建一个新的根节点 V，原先的整棵树将作为 V 的左子树。
	
	public TreeNode addOneRow(TreeNode root, int val, int depth) {
		//添加一个深度为0的节点作为伪根节点，实际上的根是它的左孩子
		TreeNode new_root = new TreeNode(0);
		new_root.left = root;
		
		//一个记录入队的节点，一个记录其深度
		LinkedList<TreeNode> q_node = new LinkedList<>();
		LinkedList<Integer> q_level = new LinkedList<>();
		
		q_node.addLast(new_root);
		q_level.addLast(0);
		
		while(!q_node.isEmpty()) {
			TreeNode node = q_node.poll();
			int node_dep = q_level.poll();
			//层次遍历代码
			if(node_dep + 1 == depth) {
				TreeNode left = node.left;
				TreeNode right = node.right;
				node.left = new TreeNode(val);
				node.left.left = left;
				node.right = new TreeNode(val);
				node.right.right = right;
			}
			
			//*********
			if(node.left != null) {
				q_node.addLast(node.left);
				q_level.addLast(node_dep+1);
			}
			
			if(node.right != null) {
				q_node.addLast(node.right);
				q_level.addLast(node_dep+1);
			}
		}
		return root.left;
    }
}






